class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}
/**
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 合并两个有序的链表
 * @param l1 
 * @param l2 
 */
const mergeTwoLists = (l1: ListNode | null, l2: ListNode | null): ListNode | null => {
    // 只要一个为空, 直接返回另一个
    if (l1 === null) return l2
    if (l2 === null) return l1

    // 两个指针分别指向l1和l2
    let l: ListNode | null = l1,
        r: ListNode | null = l2;

    // 虚拟头节点
    const dummyHead = new ListNode(0);
    let dHead = dummyHead;

    while (l !== null && r !== null) {
        if (l.val < r.val) {
            // 左边比较大
            dHead = dHead.next = l;
            l = l.next;
        } else {
            // 右边比较大
            dHead = dHead.next = r;
            r = r.next;
        }
    }
    // 左右还有没执行完的
    dHead.next = l === null ? r : l
    return dummyHead.next;
};



const mergeTwoLists3 = (l1: ListNode | null, l2: ListNode | null): ListNode | null => {
    // 只要一个为空, 直接返回另一个
    if (l1 === null) return l2
    if (l2 === null) return l1

    // 两个指针分别指向l1和l2
    let l: ListNode | null = l1,
        r: ListNode | null = l2;

    // 虚拟头节点
    const dummyHead = new ListNode(0);
    let dHead = dummyHead;

    while (l !== null || r !== null) {
        if (l == null) {
            // 左边为空
            dHead = dHead.next = r!;
            r = r!.next
        } else if (r === null) {
            // 右边为空
            dHead = dHead.next = l!;
            l = l!.next
        } else {
            // 都不为空
            if (l.val < r.val) {
                // 左边比较大
                dHead = dHead.next = l;
                l = l.next;
            } else {
                // 右边比较大
                dHead = dHead.next = r;
                r = r.next;
            }
        }

    }

    return dummyHead.next;
};

const mergeTwoLists2 = (l1: ListNode | null, l2: ListNode | null): ListNode | null => {
    // 只要一个为空, 直接返回另一个
    if (l1 === null) return l2
    if (l2 === null) return l1

    // 两个指针分别指向l1和l2
    let l: ListNode | null = l1,
        r: ListNode | null = l2;

    // 虚拟头节点
    const dummyHead = new ListNode(0);
    let dHead = dummyHead;

    while (l !== null && r !== null) {
        if (l.val < r.val) {
            // 左边比较大
            dHead = dHead.next = l;
            l = l.next
        } else {
            // 右边比较大
            dHead = dHead.next = r;
            r = r.next;
        }
    }

    // 左边还没完
    while (l !== null) {
        dHead = dHead.next = l
        l = l.next
    }

    // 右边还没完
    while (r !== null) {
        dHead = dHead.next = r;
        r = r.next;
    }

    return dummyHead.next;
};

export { }